// https://www.lintcode.com/problem/delete-digits/

public class Solution {
    /**
     * @param A: A positive integer which has N digits, A is a string
     * @param k: Remove k digits
     * @return: A string
     */
    public String DeleteDigits(String A, int k) {
        // write your code here
        StringBuilder ret = new StringBuilder();
        int start = 0;
        int m = A.length() - k;
        while (m > 0) {
          int idx = _min(A, start, m);
          if ((ret.length() != 0) || (A.charAt(idx) != '0')) {
            ret.append(A.charAt(idx));
          }
          start = idx + 1;
          --m;
        }
        return (ret.length() > 0) ? ret.toString() : "0";
    }

    protected int _min(String A, int start, int k) {
      int idx = start;
      for (int i = start + 1; i < (A.length() - k + 1); ++i) {
        if (A.charAt(i) < A.charAt(idx)) {
          idx = i;
        }
      }
      return idx;
    }
}